<?php
/**
 * @title 40. 组合总和 II - 优化去重
 * @author start2004
 */

// ini_set("memory_limit", "128M");

// class Solution {
//
//     function find() {
//
//     }
// }


class Solution {

    /**
     * @param Integer[] $candidates
     * @param Integer $target
     * @return Integer[][]
     */
    function combinationSum2($candidates, $target) {
        /**
         * @since 2020-09-10 排序
         */
        sort($candidates);

        /**
         * @since 2020-09-10 求解
         */
        $result = self::find($candidates, $target, 0, count($candidates));

        /**
         * @return
         */
        return $result;
    }

    /**
     * @title 返回和=target的排列
     * @author start2004
     * @since 2020-09-10 Created
     *
     * @param array $candidates
     * @param int $target
     * @param int $key
     * @param int $len
     * @return array|array[]
     */
    public function find($candidates = [], $target = 0, $key = 0, $len = 0){
        /**
         * @since 2020-09-10 防止溢出
         */
        if($key == $len){
            return [];
        } else {}
        $val = $candidates[$key];

        /**
         * @since 2020-09-10 结果集
         */
        $result = [];

        /**
         * @since 2020-09-10 后续即使符合和 = target, 也是相同值重复
         */
        if($target == $val){
            $result = [[$val]];
        } elseif ($target > $val){
            $result = [];

            for($i=$key+1; $i<$len; $i++){
                if($candidates[$i] != $val){
                    /**
                     * @since 2020-09-10 val存在数量0
                     */
                    $result = array_merge($result, self::find($candidates, $target, $i, $len));
                    break;
                } else {
                }
            }

            /**
             * @since 2020-09-10 val存在数量从1到$i-$key个
             */
            $t = $target;
            $valArray = [];
            for ($j=1; $j<=($i-$key); $j++){
                $valArray[] = $val;
                $t = $t - $val;
                if($t == 0){
                    $datas = [];
                    $result[] = $valArray;
                } else {
                    $datas = self::find($candidates, $t, $i, $len);
                }

                /**
                 * @since 2020-09-10 添加val元素
                 */
                foreach ($datas as $data){
                    $result[] = array_merge($data, $valArray);
                }
            }
        } else {
            /**
             * @since 2020-09-10 target < val, 因为升序, 后续无解
             */
        }

        /**
         * @return
         */
        // echo "key={$key}, target={$target}", PHP_EOL;
        // var_dump($result);
        // echo str_repeat(PHP_EOL, 2);
        return $result;
    }
}


/**
 * @url http://127.0.0.1/leetcode/202009/2020.09.10_2.php
 */
$datas = [
    // [[10,1,2,7,6,1,5], 8],
    [[1,1,1,1], 3],
    [[1,1,1,2,3], 5],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    // var_dump($data);

    $obj = new Solution();
    $result = $obj->combinationSum2(...$data);
    // $result = $obj->find(...$data);
    var_dump($result);
    // if(count($result)<=20){
    //     var_dump($result);
    // } else {
    //     var_dump(count($result));
    // }
    echo str_repeat("<br>", 3);
}

// foreach ($datas as $data){
//     $obj = new $data[0][0](...$data[1][0]);
//
//     for ($i=1; $i<count($data[0]); $i++){
//         $result = $obj->$data[0][$i](...$data[1][$i]);
//
//         echo $data[0][$i] ."(\"". $data[1][$i][0] ."\") ";
//             if($result === true){
//                 echo "True";
//             } elseif($result === false) {
//                 echo "False";
//             } elseif($result === null) {
//                 echo "Null";
//             } elseif(is_array($result)) {
//                 var_dump($result);
//             } else {
//                 echo $result;
//             }
//         echo PHP_EOL;
//     }
//
//     echo str_repeat(PHP_EOL, 3);
// }
$xhprof->end();
